#include <cmath>
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>
#include <set>
#include <cstring>
#include<iomanip>
#define endl "\n"
using namespace std;
bool p[1000010];
int kk[1000010];
void zhi(int n)
{
	for(int i=2;i<=n;i++)
	{
		if(p[i]!=0)
		{
			kk[i]=kk[i-1];
		}
		else
		{
			kk[i]=kk[i-1]+1;
			for(int j=2*i;j<=n;j=j+i)
			{
				p[j]=1;
			}
		}
	}
}
int main()
{
	int N,n,l,r;
	
	cin>>N>>n;
	zhi(n);
	while(N--)
	{
		cin>>l>>r;
		if(l<1||r>n)
		{
			cout<<"Crossing the line"<<endl;
	
		}	
		else
		
		cout<<kk[r]-kk[l-1]<<endl;
	}
	return 0;
}